'''
Created on Nov 24, 2012

@author: trananh
'''

class Node(object):
    """
    Implements a simple binary node that uses the Median splitting strategy.
    
    Reference(s):
        - O'Hara, Stephen, and Bruce A. Draper. "Scalable action recognition
            with a subspace forest." Computer Vision and Pattern Recognition
            (CVPR), 2012 IEEE Conference on. IEEE, 2012.
    """
    
    # Node status enum
    COLLECTING = 1
    SPLITTING = 2
    
    # Algorithm parameters
    Capacity = 25                           # Max number of items each node can hold (default: 21)

    def __init__(self, capacity=None, featuresIdx=None):
        """
        Constructs a new node.
        
        PARAMETER(S):
            capacity - sets the capacity of the node (static variable).
            featuresIdx - specifies which features of each data item(s) to consider
                when building the tree.
        """
        self.status = Node.COLLECTING
        self.items = list()                 # list of items
        self.pivot = None                   # pivot item
        self.threshold = None               # splitting threshold
        self.leftChild = None               # left child
        self.rightChild = None              # right child
        if capacity is not None:
            Node.Capacity = capacity
        self.featuresIdx = featuresIdx      # specifies which features of each contained data
                                            # item(s) to consider (default to all)
    
    def addAll(self, items):
        """
        Adds all the new items to the node.
        
        PARAMETERS:
            items - list of new items to be added.
        """
        for i in items:
            self.add(i)
            
    def add(self, item):
        """
        Adds a new item to the node.
        
        PARAMETERS:
            item - a new item to be added.
        """
        if self.status == Node.COLLECTING:
            self.items.append(item)
            if len(self.items) > Node.Capacity:
                self.pivot = self.selectPivot()
                if self.checkSplittingCriteria():
                    # split the node
                    self.threshold = self.selectThreshold()
                    if self.threshold is not None:
                        self.leftChild = self.__class__(featuresIdx=self.featuresIdx)
                        self.rightChild = self.__class__(featuresIdx=self.featuresIdx)
                        for x in self.items:
                            D = self.pivot.distance(x,featuresIdx=self.featuresIdx)
                            if D <= self.threshold:
                                self.leftChild.add(x)
                            else:
                                self.rightChild.add(x)
                        self.status = Node.SPLITTING
                        self.items = None
        else:
            D = self.pivot.distance(item,featuresIdx=self.featuresIdx)
            if D <= self.threshold:
                self.leftChild.add(item)
            else:
                self.rightChild.add(item)
    
    def checkSplittingCriteria(self):
        """
        Checks to see if the items within the node pass the splitting criteria.
            - Median Splitting: The node is always split when the number
                of items surpass the maximum limit.
        """
        return True
    
    def selectPivot(self):
        """
        Selects an item to be the pivot point.
            - Median Splitting: The pivot is randomly selected from the collection
                of items in the node.
        """
        from random import choice
        return choice(self.items)
    
    def selectThreshold(self):
        """
        Selects a threshold for splitting.
        Returns None if none could be found (e.g., all items yielding exactly the same
        distance from the pivot and a median cannot be computed, that is all items in
        this node are indistinguishable).
            - Median Splitting: The threshold is set to the median distance between
                the pivot element and items in the node.
        '"""
        distances = [self.pivot.distance(x,featuresIdx=self.featuresIdx) for x in self.items] 
        from utils import utils
        return None if len(set(distances)) <= 1 else utils.median(distances)
    
    def query(self, item):
        """
        Finds the node that would best match the queried item.
        
        PARAMETERS:
            item - the item to query.
        """
        if self.status != Node.SPLITTING:
            return self
        D = self.pivot.distance(item,featuresIdx=self.featuresIdx)
        if D <= self.threshold:
            return self.leftChild.query(item)
        else:
            return self.rightChild.query(item)
